// 动态规划：leftMax[i]表示i及i左边最大高度，rightMax[i]表示i及i右边最大高度，分别对应从左看和从右看；
// 分别正向和逆向遍历数组得到leftMax和rightMax数组；
// i出能接到雨水高度=min(leftMax[i], rightMax[i]) - height[i];
// 再次遍历累加求和。
// time: O(3n)即O(n), space: O(2n)即O(n)。
func trap(height []int) int {
	n := len(height)
	if n == 0 {
		return 0
	}

	leftMax := make([]int, n)
	leftMax[0] = height[0]
	for i := 1; i < n; i++ {
		leftMax[i] = max(leftMax[i-1], height[i])
	}

	rightMax := make([]int, n)
	rightMax[n-1] = height[n-1]
	for i := n - 2; i >= 0; i-- {
		rightMax[i] = max(rightMax[i+1], height[i])
	}

	sum := 0
	for i := 0; i < n; i++ {
		sum += min(leftMax[i], rightMax[i]) - height[i]
	}

	return sum
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}